package org.xingole.leetcode.dp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/shopping-offers/description/">
 * Problem Description</a>
 */
public class ShoppingOffers {

    /**
     * map stores the minimum cost corresponding to this set of needs.
     */
    final Map<List<Integer>, Integer> map = new HashMap<>();

    /**
     * 
     * @param price an integer array price where price[i] is the price of the ith
     * item.
     * @param special an array where special[i] is of size n + 1 where special[i][j]
     * is the number of pieces of the jth item in the ith offer and special[i][n] is
     * the price of the ith offer.
     * @param needs an integer array where needs[i] is the number of pieces of the ith
     * item you want to buy.
     * @return the lowest price you have to pay for exactly certain items as given, where
     * you could make optimal use of the special offers. You are not allowed to buy more
     * items than you want, even if that would lower the overall price. You could use any
     * of the special offers as many times as you want.
     */
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        /*
         * Approach: Using Recursion with Memoization
         *
         */
        return shopping(price, special, needs);
    }

    /**
     * Returns the minimum cost of buying these items as required by this needs list.
     * 
     * @param price
     * @param special
     * @param needs the current needs
     * @return
     */
    private int shopping(List<Integer> price, List< List<Integer> > special, List<Integer> needs) {

        if (map.containsKey(needs)) {
            return map.get(needs);
        }

        int j = 0;
        // 1. Determine the cost of buying items as per the needs array, without applying 
        // any offer.Store the result in res.
        int res = dot(needs, price);

        // 2. Iterate over every offer in the special list. For every offer chosen, repeat
        // steps 3 to 5.
        for (var s : special) {
            // 3. Create a copy of the current needs in a clone list(so that the original
            // needs can be used again, while selecting the next offer).
            var clone = new ArrayList<>(needs);
            for (j = 0; j < needs.size(); j++) {
                // 4. Try apply the current offer. If possible, update the required
                // number of items in clone.
                int diff = clone.get(j) - s.get(j);
                if (diff < 0) {
                    break;
                }
                clone.set(j, diff);
            }

            // 5. If the current offer could be applied, find the minimum cost.
            if (j == needs.size()) {
                res = Math.min(
                    res, 
                    s.get(j) + shopping(price, special, clone)
                );
            }
        }

        // 6. Return the res corresponding to the minimum cost.
        map.put(needs, res);
        return res;
    }

    private int dot(List<Integer> a, List<Integer> b) {
        int sum = 0;
        for (int i = 0; i < a.size(); i++) {
            sum += a.get(i) * b.get(i);
        }

        return sum;
    }
}
